﻿#define _CRT_SECURE_NO_WARNINGS 1
//最长上升子序列II
//给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。
//输入格式
//第一行包含整数 N。
//第二行包含 N个整数，表示完整序列。
//输出格式
//输出一个整数，表示最大长度。
//数据范围
//1≤N≤100000，−109≤数列中的数≤109
//输入样例：
//7
//3 1 2 1 8 5 6
//输出样例：
//4
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int a[N];
int q[N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);//读入数据

    int len = 0;//一开始的长度为0
    for (int i = 0; i < n; i++)//遍历每一个数据
    {
        //是用二分法来查找那个最大的小于a[i]的数，然后用它来覆盖他之后的那一个长度的最小值，
        //举例，比如现在我二分查找到的最大的小于a[i]的值是4，而5一定是大于或等于他的，
        //那么此时又因为a[i]加到了长度为4子序列，让他的长度变成了5，
        //那么此时最小的长度为5的子序列结尾应该就是a[i]，那么就得把5的结尾更新成a[i]
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;//这里如果q[mid]<a[i]那么就意味着真正的数在mid右边，当然也有可能是他本身，因此l=mid
            else r = mid - 1;//这里也同理，但因为他肯定在要求外，所以是mid-1
        }
        len = max(len, r + 1);//这里需要取max，因为我们算的是最长子序列，假如此时r+1比原来的len长，那么就得更新，也方便后续的二分
        q[r + 1] = a[i];//这里就和二分时的解释一样，需要更新结尾最小值
    }
    printf("%d\n", len);
}